//
// Created by liushuai on 2021/2/5.
//

#include "sortInList.h"
ListNode* sortInList(ListNode* head) {
  ListNode* current = head;
  if (!current || !current->next)
    return current;
  else {
    int currentValue = current->val;
    ListNode* nextNode = current->next;
    int nextValue = nextNode->val;
    if (currentValue <= nextValue)
      current->next = sortInList(current->next);
    else {
      ListNode* temp = nextNode->next;
      current->next = temp;
      nextNode->next = sortInList(current);
      current = nextNode;
    }
    return current;
  }
}